The present invention relates to computer-assisted methods and apparatus for generating or compiling electronic designs such as designs for digital integrated circuits. More specifically, the invention relates to improvements in using timing information while compiling electronic designs.
Electronic design automation (xe2x80x9cEDAxe2x80x9d) is becoming increasingly complicated and time consuming, due in part to the greatly increasing size and complexity of the electronic devices designed by EDA tools. Such devices include general purpose microprocessors as well as custom logic devices including Application Specific Integrated Circuits (xe2x80x9cASICsxe2x80x9d). Examples of integrated circuits include non-programmable gate arrays, field programmable gate arrays (xe2x80x9cFPGAsxe2x80x9d), and complex programmable logic devices (xe2x80x9cPLDsxe2x80x9d or xe2x80x9cCPLDsxe2x80x9d). The design of even the simplest of these devices typically involves generation of a high level design, logic simulation, generation of a network, timing simulation, etc.
Meeting timing requirements is important to the correct operation of an integrated circuit. For example, for a plurality of D-type flip-flops (xe2x80x9cDFFsxe2x80x9d) to feed through some logic to another plurality of DFFs, it is generally required that the signals from the first set of DFFs must finish propagating through any intermediate logic and have settled to their final state on the D-input of each of the destination DFFs before the next rising edge of the clock. (In fact they must finish before the next clock edge by an amount known as the setup delay of the register Tsu.) If the delay through the resulting logic is greater than the time between rising clock edges, then the state that the destination DFFs will hold on the next clock edge will be undefined.
In order to implement a source electronic design, such as might be represented by a schematic or netlist among other possibilities, into a hardware device, such as a PLD or CPLD, several steps are used to generate an efficiently implemented design. BTwo of these steps are placement and routing. Placement and routing are responsible for assigning logic elements in a source electronic design to individual locations in the target device, such a s a programmable logic device. Most circuit optimization methods, such as those occurring during placement and routing, depend upon an identification of xe2x80x9ccritical connectionsxe2x80x9d between circuit elements or blocks. A delay for a path will be the sum of delays on its constituent connections. Critical paths include those signal paths with excessive delays and that play an important role in limiting the performance of the electronic design implemented in the hardware device. There may be several critical paths in a circuit. The cycle time of the clock that controls the DFF""s at the beginning and end of the path cannot be any less than this delay. A critical path may consist of one or more connections, and all those connections will be critical. Those connections lying on critical paths will be labeled critical connections and are described as having high criticality. Emphasis is made during optimization to optimize the timing of those connections having the greatest criticality. For example, during placement, the placement algorithm will attempt to keep those elements or blocks having a critical connection in a configuration where the connection would be made with as little delay as possible, i.e. by interconnecting the elements or blocks with fast wiring lines.
Prior approaches have computed the criticality of a connection based on its xe2x80x9cslackxe2x80x9d. The slack of a connection is the amount of delay that could be added to a connection without causing any timing constraint depending on that connection to be violated. Stated another way, for a given connection, slack is the deviation of the calculated arrival time made by timing analysis from the required arrival time specified by the designer. See xe2x80x9cUse of Slack as a Measurement of Being On Time and the Procedure for Calculating Slack,xe2x80x9d IBM Technical Disclosure Bulletin, November 1982, pp. 2826-2830. Negative slacks indicate that the calculated path timing exceeds the timing constraint. Criticality is an inverse function of slack. Connections with low, zero, or negative slack have a high criticality.
One method of timing analysis currently used in circuit optimization estimates the slack of each connection to determine which connections are critical and therefore need to be made or placed using fast wiring lines to avoid slowing down the circuit. For example, in implementing a design into a programmable logic device, a placement and routing tool would assign the source design logic elements to individual locations on the device. To minimize delay in a hierarchical architecture device, the connection between logic elements might use a local connection, i.e. occurring within the same logic array block (xe2x80x9cLABxe2x80x9d), as the xe2x80x9cfast wiringxe2x80x9d. In other devices, the xe2x80x9cfastxe2x80x9d wiring might be determined by minimizing the length of the connection between the two logic elements. Current methods have difficulty in identifying the most critical of the connections. For example, current methods on some occasions, fail to differentiate between connections having identical slacks but lying on different paths having different relative margins for additional delay. This may occur, for example, when a connection is on a path having a relatively large timing constraint, e.g., 100 nanoseconds (xe2x80x9cnsxe2x80x9d). On some of such paths, there may be little margin for additional delay. Yet, the connection at issue may possess the same slack value (say 2 nanoseconds) as another connection that is on a different path that has a relatively small timing constraint, say 4 nanoseconds. While the slack based criticality of the two connections is identical, their true criticality is rather different. The first path has very little slack remaining relative to the length of the timing constraint on which it lies (98 nanoseconds of the 100 nanosecond delay budget for the path is used up). So it is more likely that the timing constraint on the first connection here will be violated than the timing constraint on the second connection.
Under current approaches, an initial timing analysis will often yield several connections having a negative slack. These negative slacks generally must be dealt with separately in a criticality computation and tend to lead to many connections with high criticality. Excessive numbers of connections with high criticality tend to make the optimization tools behave poorly because they are attempting to optimize too many connections at once and, as a result, optimize all connections poorly. Another problem to be addressed, them, is how to deal with negative slack connections so that the portion of negative slack connections with the highest criticality are optimized first. What is needed is an improved method for determining criticality.
The present invention provides a method of generating an electronic design. Optimizing the timing of a circuit relies on methods of identifying critical connections between circuit elements or blocks. Extra effort is made during optimization to ensure that connections with the highest criticality have their timing optimized. The invention provides a new method of computing the criticality of connections in electronic systems with multiple timing constraints. The criticality is computed as a function of slack ratio. Slack is the amount of delay that can be added to a connection without causing any timing constraint depending on that connection to be violated. The slack ratio of a path is the slack of that path divided by the magnitude of the timing constraint applicable to that path. Connections typically lie on multiple paths, each of which is potentially governed by a different timing constraint. The slack ratio of a connection is the minimum slack ratio of all the paths that pass through that connection. An electronic representation of the electronic design is received which includes various connections between various blocks specifying functions performed within the electronic design. Each of the connections forms part of one or more paths through at least a portion of the electronic design. At least one of the paths have an associated timing constraint. The method assigns criticality values to at least one of the connections. These criticality values are based upon a slack ratio that is a function of the timing constraints and values of slack for paths on which the connections reside. The method furthermore revises the electronic representation in a manner that biases the representation toward a state in which individual connections having relatively high criticality are not changed in a manner which increases the delay or changes them in a manner which reduces delay.
Another aspect of the invention provides a method for generating an electronic design wherein the timing constraints for a path and all coupled paths are relaxed when a connection has a negative slack ratio. An electronic representation of the electronic design is received which includes various connections between various blocks specifying functions performed within the electronic design. Each of the connections forms part of one or more paths through at least a portion of the electronic design. At least one of the paths have an associated timing constraint. The method relaxes the timing constraint for a path and any coupled timing constraints proportionately. Criticality values are assigned to at least one of the connections and the electronic representation is revised, biased towards a state in which individual connections having relatively high criticality are changed in a manner that reduces delay. In yet another aspect, the present invention provides a method for relaxing timing constraints and coupled timing constraints proportionately when routability problems occur.
These and other features and advantages of the present invention are described below with reference to the drawings.